The present invention relates to digital computer systems, and more particularly, to digital data compression and decompression schemes employed in digital computer systems.
Digital computer systems perform data compression to realize a more efficient use of finite storage space. The computer system typically includes a hardware component referred to as a compression accelerator, which accepts work requests or data requests from the host system to compress or decompress one or more blocks of the requested data. When designing an accelerator to perform compression, there is a tradeoff between the size of the input data that is to be compressed compared to the possible compression ratio and the latency that results from compressing the data.
Compression accelerators often utilize a “DEFLATE” algorithm, which is a lossless compression scheme that combines the Lempel-Ziv (e.g., LZ77) compression algorithm with a Huffman encoding algorithm to perform the compression. The computed output from the Huffman algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). The Huffman algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol.
To maximize the compression ratio achieved using the DEFLATE algorithm, symbols are encoded into the variable-length code table according to their frequency of occurrence. In other words, the most frequent symbols are encoded with the fewest bits, while relatively less common symbols are encoded with relatively more bits. This results in a direct reduction in the required storage space for the compressed data stream. Because the symbols are encoded based on their relatively frequencies, the occurrence counts for each symbol must be sorted. Sorting the symbol counts (frequencies) during this process is expensive in terms of area (the number of latches and width comparators required), power, and timing/wiring considerations.